package com.cskaoyan.javase.recursion._3hanoi;

/**
 * 汉诺塔问题
 * 相传在古印度的圣庙中，有一种被称之为汉诺塔（也叫河内塔，Hanoi）的游戏
 * 简单来说：有三个塔1，2，3，塔1上有 N 个（N>0）穿孔圆盘，大盘在下，小盘在上
 * 要求按下列规则将所有圆盘移至塔3：
 * 	1，每次只能移动一个圆盘
 * 	2，大盘一定在小盘之下
 * 提示：可将圆盘临时置于塔2，也可以将塔1的圆盘重新移回塔1，但都必须遵循上述两条规则
 * 问：当塔1上有N（N>=1）个圆盘时，最少要移动多少次？（注意是最少）
 *
 * 当N=1时,需要1次就行
 * 当N=2时,先把最小盘子移到塔2上,再把最大的盘子移到塔3上,最后再把最小的盘子移到塔3上,一共三步.
 * 当N=3时,先把最小的盘子移到塔3上,再把中间的盘子移到塔2上,然后把最小的盘子移到塔2上去,再把最大的盘子移到塔3中.随后
 *      再把最小的盘子从塔2移到塔1,再把中间盘子移到塔3,最后把最小的盘子从塔1移到塔3.一共需要7步.
 * 当N=4时....
 *
 * 递归的思想是分解的思想,你能够找到规律吗?能够找到分解问题的方式吗?
 * 求解汉诺塔问题,必然存在的一步是: 把塔1上最大的盘子移到塔3上去,这时塔3一定是空的
 * 为了保证塔3是空的,所以需要先把塔1上,最大盘子外的所有盘子都移到塔2上去
 * 最后只要再把塔2中的所有盘子,全部移到塔3上去就可以了.
 *
 * 所以就有了分解的思路,假如需要f(N)步完成汉诺塔问题,N是盘子的个数,完成汉诺塔问题就需要三步走:
 *      1.先把N-1个盘子从塔1到塔2 ,共需要f(N-1)步
 *      2.把最大的盘子从塔1到塔3, 共需要1步
 *      2.再把N-1个盘子从塔2到塔3, 共需要f(N-1)步
 * 于是f(N) = f(N-1)+ 1 + f(N-1)
 * 最后f(1) = 1;
 *
 * f(N) = 2f(N-1)+1 求解通项公式
 * 两边都加1
 * f(N) + 1 = 2(f(N-1) + 1)
 * f(N) + 1 / f(N-1) + 1 = 2
 * f(N) = 2的n次方 - 1
 *
 *
 * @since 11:26
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(hanoi(30));
    }

    // 递归求解汉诺塔问题,n是盘子的个数
    public static long hanoi(int n) {
        // 先写出口
        if (n == 1) {
            return 1;
        }
        // 递归体
        return hanoi(n - 1) + 1 + hanoi(n - 1);
    }
}
